
/**
 *  给定初始单词，结束单词，以及单词列表
 *	要求找到最短的路径从初始到结束。相邻单词有且只有一个字母不同
 *	成批扩展
 * 
 */
#include <bits/stdc++.h>
using namespace std;

class Solution {
using vi = vector<int>;
map<string, int> Map;	
vector<vi> G;
int N;
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        N = wordList.size() + 1;
		Map[beginWord] = 1;
		for(int i=0;i<wordList.size();++i){
			const auto & si = wordList[i];
			if(si == beginWord) continue;
			Map[si] = i + 2;
		}     

        G.assign(N + 1, {});
		for(int i=0;i<wordList.size();++i){
			if(isOK(beginWord, wordList[i])){
                G[1].emplace_back(i + 2);
				G[i + 2].emplace_back(1); 
			}
			for(int j=i+1;j<wordList.size();++j){
                if(isOK(wordList[i], wordList[j])){
					G[i + 2].emplace_back(j + 2);
					G[j + 2].emplace_back(i + 2);
				}
			}
		}

		auto it = Map.find(endWord);
		if(it == Map.end()) return 0;
		auto dst = it->second;

        vi Flag(N + 1, 0);
		queue<int> Q;
		Q.push(1);
		Flag[1] = 1;
		int ans = 0;
		size_t sz = 0;
		while(sz = Q.size()){
			++ans;
            while(sz--){
                auto h = Q.front(); Q.pop();
				for(auto v : G[h]){
					if(Flag[v]) continue;
					if(v == dst) return ans + 1;
					Flag[v] = 1;
					Q.push(v);
				}
			}
		}
		return 0;
    }

	bool isOK(const string & s, const string & t){
		int c = 0;
		for(int i=0;i<s.length();++i){
            if(s[i] != t[i]){
				if((c += 1) > 1) return false;
			}
		}
		return 1 == c;
	}
};